package com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.快速排序;

import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.Helper;
import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.IMutableSorter;

import java.util.List;

/**
 * 快速排序 第二版
 *
 * @author Baixiaowen
 */
public class QuickSortV2 implements IMutableSorter {

    @Override
    public void sort(int[] A) {
        this.quickSort(A, 0, A.length);
    }

    private void quickSort(int[] A, int l, int r) {

        if (r - l <= 1) {
            return;
        }

        // 选择最左边的元素构造子问题集合
        // 小于x的放到左边，大于x的放到右边
        // int x = A[l];
        // i代表x的位置
        int i = partition(A, l, r);

        // 省略计算x所在位置i
        // 以及将所有小于x的元素放到左边，大于x元素放到右边的
        quickSort(A, l, i);
        quickSort(A, i + 1, r);
    }

    private int partition(int[] A, int l, int r) {
        int x = A[l];

        // i 指向左边不能确定的值
        int i = l + 1;
        // j 指向右边不能确定的值 + 1
        int j = r;

        // x | -- left -- | -- mid -- | -- right -- |
        while (i != j) {
            if (A[i] < x) {
                i ++;
            } else {
                Helper.swap(A, i, --j);
            }
        }

        Helper.swap(A, i - 1, l);
        return i - 1;
    }
}
